package class08;

public class Code07_Knapsack {

	/**
	 * 方法一：暴力尝试
	 * @param weights
	 * @param values
	 * @param bag
	 * @return
	 */
	public static int maxValue1(int[] weights, int[] values, int bag) {
		//return process1(weights, values, 0, 0, bag);
		return process2(weights, values, 0, 0, 0, bag);
	}

	// 该函数表示  i...end 的货物自由选择，所形成的最大价值返回。  process1 不包含前面的价值
	// bag表示不要超过的重量
	// alreadyweight 之前做的决定所达到的重量
	public static int process1(int[] weights, int[] values,
							   int i, int alreadyweight, int bag) { // i表示来到了第i号货物
		if (alreadyweight > bag) { // 超重了，该方案获取的价值为0
			return 0;
		}
		if (i == weights.length) { // i越界了，它当前不产生价值
			return 0;
		}

//		if (alreadyweight + weights[i] < bag) { // todo： ？？这个有问题要修改
//			return 0;
//		}
			return Math.max(

					process1(weights, values, i + 1, alreadyweight, bag), // 不要货物i，它自然不产生价值，也不会增加重量；后序价值让后面i+1决定吧

					values[i] + process1(weights, values, i + 1, alreadyweight + weights[i], bag)); // 要货物i，会增加重量；价值让后面i+1决定吧


	}


	// process2 带上之前的重量 ==> 这个没问题
	public static int process2(int[] weights, int[] values,
							   int i, int alreadyWeight, int alreadyValue, int bag) {
		if (alreadyWeight > bag) {
			return 0;
		}
		if (i == values.length) {
			return alreadyValue;
		}
		return Math.max(
				process2(weights, values, i+1, alreadyWeight, alreadyValue, bag), // 不要i物品
				process2(weights, values, i+1,
						alreadyWeight + weights[i],
						alreadyValue + values[i], bag)); //要i物品
	}



	/**
	 * 方式二：动态规划
	 * @param c
	 * @param p
	 * @param bag
	 * @return
	 */
	public static int maxValue2(int[] c, int[] p, int bag) {
		int[][] dp = new int[c.length + 1][bag + 1];
		for (int i = c.length - 1; i >= 0; i--) {
			for (int j = bag; j >= 0; j--) {
				dp[i][j] = dp[i + 1][j];
				if (j + c[i] <= bag) {
					dp[i][j] = Math.max(dp[i][j], p[i] + dp[i + 1][j + c[i]]);
				}
			}
		}
		return dp[0][0];
	}

	public static void main(String[] args) {
		int[] weights = { 3, 2, 4, 7 };
		int[] values = { 5, 6, 3, 19 };
		int bag = 11;
		System.out.println(maxValue1(weights, values, bag));
		System.out.println(maxValue2(weights, values, bag));
	}

}

/**todo：递归的尝试原则: 要找到 可变参数 最少，形式最简单的方式。（不在意固定参数）
 * 形式最简单：最好是个值，而不是链表，数组等
 *
 * 目的：方便改动态规划
 */